class Solution:
    def match(self, left, right):
        if (left == '(' and right == ')') or (left == '{' and right == '}') or (left == '[' and right ==']'):
            return True
        return False

    # @param {string} s
    # @return {boolean}
    def isValid(self, s):
        st = []
        for i in range(0, len(s)):
            if not len(st):
                st.append(s[i])
            else:
                if self.match(st[-1], s[i]):
                    st.pop()
                elif s[i] == '{' or s[i] == '[' or s[i] == '(':
                    st.append(s[i])
                else:
                    return False
        if len(st):
            return False
        return True

print Solution().isValid('()')
print Solution().isValid('()[]{}')
print Solution().isValid('(]')


        
